package com.tongji.diy.utils
{
	import flash.geom.Point;
	
	import de.polygonal.ds.DListNode;
	
	/**
	 * 
	 * @author frank
	 * 
	 */
	public class PolygonMath
	{
		public function PolygonMath()
		{
		}
		
		//对于两个矩形包围盒进行分离轴测试，测试结果返回值0<i<2时是boundingBoxA的第i个顶点索引，即boundingBoxA[i],boundingBoxA[i+1]连线所形成的直线就是分离轴;
		//测试结果返回值2<=i<4时是boundingBoxB的第i-2个顶点索引，即boundingBoxB[i-2],boundingBoxA[i-1]连线所形成的直线就是分离轴;
		//若返回值是-1则说明不存在分离轴使两矩形进行分离，即两矩形相交
		//两个输入变量是两个矩形包围盒的顶点坐标
		public static function rectangleSeparatingAxisCollisionTest(boundingBoxA:Vector.<Point>, boundingBoxB:Vector.<Point>):int
		{
			for(var i:int = 0; i < boundingBoxA.length + boundingBoxB.length; i++)
			{
				var coefficientVector:Vector.<Number>;
				var A:Number; 
				var B:Number;
				var C:Number;
				var sign:int = 1;
				var j:int = 0;
				if(i < boundingBoxA.length)
				{
					coefficientVector = buildLineAccrodingTwoPoints(boundingBoxA[i],boundingBoxA[(i+1) % boundingBoxA.length]);
					A = coefficientVector[0];
					B = coefficientVector[1];
					C = coefficientVector[2];
					
					if(boundingBoxA[(i+2) % boundingBoxA.length].x*A + boundingBoxA[(i+2) % boundingBoxA.length].y*B + C > 0)
						sign = -1;
					for(j = 0; j < boundingBoxB.length; j++)
					{
						if((boundingBoxB[j].x*A + boundingBoxB[j].y*B + C)*sign < 0)
							break;
					}
					
					if(j == boundingBoxB.length)
						return i;
				}
				else
				{
					coefficientVector = buildLineAccrodingTwoPoints(boundingBoxB[i-boundingBoxA.length],boundingBoxB[(i-boundingBoxA.length+1) % boundingBoxA.length]);
					A = coefficientVector[0];
					B = coefficientVector[1];
					C = coefficientVector[2];
					
					if(boundingBoxB[(i - boundingBoxA.length + 2) % boundingBoxB.length].x*A + boundingBoxB[(i - boundingBoxA.length + 2) % boundingBoxB.length].y*B + C > 0)
						sign = -1;
					for(j = 0; j < boundingBoxA.length; j++)
					{
						if((boundingBoxA[j].x*A + boundingBoxA[j].y*B + C)*sign < 0)
							break;
					}
					
					if(j == boundingBoxA.length)
						return i;
				}
			}
			
			return -1;
		}
		//根据两个点构建一条直线方程，返回值是方程的系数AX+BY+C的ABC
		public static function buildLineAccrodingTwoPoints(pointA:Point, pointB:Point):Vector.<Number>
		{
			var A:Number = pointA.y - pointB.y;
			var B:Number = - pointA.x + pointB.x;
			var C:Number = -pointA.x*A - pointA.y*B;
			var vector:Vector.<Number> = new Vector.<Number>;
			vector.push(A, B, C);
			return vector;
		}
		//两条边是否相交，fasle表示不想交
		public static function edgeIntersect(edgeAPointA:Point, edgeAPointB:Point, edgeBPointA:Point,edgeBPointB:Point, exceptCoincide:Boolean = false):Boolean
		{
			var coefficientVector1:Vector.<Number> = buildLineAccrodingTwoPoints(edgeAPointA,edgeAPointB);
			var coefficientVector2:Vector.<Number> = buildLineAccrodingTwoPoints(edgeBPointA,edgeBPointB);
			var A1:Number = coefficientVector1[0];
			var B1:Number = coefficientVector1[1];
			var C1:Number = coefficientVector1[2];
			var A2:Number = coefficientVector2[0];
			var B2:Number = coefficientVector2[1];
			var C2:Number = coefficientVector2[2];
			var EBPA:Number = (A1*edgeBPointA.x+B1*edgeBPointA.y+C1);
			var EBPB:Number = (A1*edgeBPointB.x+B1*edgeBPointB.y+C1);
			var EAPA:Number = (A2*edgeAPointA.x+B2*edgeAPointA.y+C2);
			var EAPB:Number = (A2*edgeAPointB.x+B2*edgeAPointB.y+C2);
			
			var judge1:Number = EBPA*EBPB;
			var judge2:Number = EAPA*EAPB;
			if((equal(EAPA,0)||equal(EAPB,0)||equal(EBPA,0)||equal(EBPB,0))&&exceptCoincide)
				return false;
			if( judge1 > 0 || judge2 > 0)
			{
				return false;
			}
			else if(judge1 < 0 && judge2 < 0)
			{
				return true;
			}
			else if(judge1 == 0 && judge2 < 0)
			{
				if(EBPA == 0)
				{
					if(edgeBPointA.x <= Math.max(edgeAPointA.x,edgeAPointB.x) || edgeBPointA.x >= Math.min(edgeAPointA.x,edgeAPointB.x)
						&& edgeBPointA.y <= Math.max(edgeAPointA.y,edgeAPointB.y) || edgeBPointA.y >= Math.min(edgeAPointA.y,edgeAPointB.y))
					{
						if(!exceptCoincide)
							return true;
						else
							return false;
					}
					else
						return false;
				}
				else
				{
					if(edgeBPointB.x <= Math.max(edgeAPointA.x,edgeAPointB.x) || edgeBPointB.x >= Math.min(edgeAPointA.x,edgeAPointB.x)
						&& edgeBPointB.y <= Math.max(edgeAPointA.y,edgeAPointB.y) || edgeBPointB.y >= Math.min(edgeAPointA.y,edgeAPointB.y))
					{
						if(!exceptCoincide)
							return true;
						else
							return false;
					}
					else
						return false;
				}
				
			}
			else if(judge2 == 0 && judge1 < 0)
			{
				if(EAPA == 0)
				{
					if(edgeAPointA.x <= Math.max(edgeBPointA.x,edgeBPointB.x) || edgeAPointA.x >= Math.min(edgeBPointA.x,edgeBPointB.x)
						&& edgeAPointA.y <= Math.max(edgeBPointA.y,edgeBPointB.y) || edgeAPointA.y >= Math.min(edgeBPointA.y,edgeBPointB.y))
					{
						if(!exceptCoincide)
							return true;
						else
							return false;
					}
					else
						return false;
				}
				else
				{
					if(edgeAPointB.x <= Math.max(edgeBPointA.x,edgeBPointB.x) || edgeAPointB.x >= Math.min(edgeBPointA.x,edgeBPointB.x)
						&& edgeAPointB.y <= Math.max(edgeBPointA.y,edgeBPointB.y) || edgeAPointB.y >= Math.min(edgeBPointA.y,edgeBPointB.y))
					{
						if(!exceptCoincide)
							return true;
						else
							return false;
					}
					else
						return false;
				}
				
			}
			else /*if(judge1 == 0 && judge2 == 0)*/
			{
				if(!exceptCoincide)
					return true;
				else
					return false;
			}
		}
		//返回值为真时说明点在多边形内部，否则点不在多边形内部
		public static function pointIsInPoly(polyControlPoint:DListNode, testPoint:Point):Boolean
		{
			var point:Point = testPoint.clone();
			var count:int = 0;
			var pCP:DListNode = polyControlPoint;
			var intersectionPointX:Number;
			while(1)
			{
				if(!equal(pCP.next.data.globalY, pCP.data.globalY))//不平行于x轴
				{
					intersectionPointX = pCP.data.globalX + (pCP.next.data.globalX - pCP.data.globalX)*(point.y-pCP.data.globalY)/(pCP.next.data.globalY - pCP.data.globalY);
					if(!equal(pCP.next.data.globalX, pCP.data.globalX) && point.x < intersectionPointX)
					{
						if(intersectionPointX < Math.max(pCP.next.data.globalX,pCP.data.globalX) && intersectionPointX > Math.min(pCP.next.data.globalX,pCP.data.globalX))
						{count++;}
					}
					else if(point.x < intersectionPointX)
					{
						if(point.y < Math.max(pCP.next.data.globalY,pCP.data.globalY) && point.y > Math.min(pCP.next.data.globalY,pCP.data.globalY) && intersectionPointX > point.x)
						{count++;}
					}
					if(equal(point.x ,intersectionPointX))
					{
						return false;
					}
				}
				else//平行于x轴
				{
					if((equal(point.y, pCP.next.data.globalY)||equal(point.y, pCP.data.globalY))&& point.x > Math.min(pCP.next.data.globalX,pCP.data.globalX) && point.x < Math.max(pCP.next.data.globalX,pCP.data.globalX))
						return false;
					else if(equal(point.y, pCP.next.data.globalY)||equal(point.y, pCP.data.globalY))
					{
						point.y = point.y-1;
						return pointIsInPoly(pCP,point);
					}
				}
				
				if(equal(pCP.data.y,point.y))
				{
					if((pCP.prev.data.y - pCP.data.y)*(pCP.data.y - pCP.next.data.y) < 0)
					{count +=2;}
					else
					{count++;}	
				}								
				pCP = pCP.next;
				if (pCP == polyControlPoint)
					break;
			}
			
			if(count%2 == 0)
				return false;
			else 
				return true;	
		}
		
		public static function equal(A:Number, B:Number, inaccuracy:Number = .01):Boolean
		{
			if(Math.abs(A - B) < inaccuracy)
				return true;
			else
				return false;
		}
		
		public static function vectorAngle(VA:Point, VB:Point):Number
		{
			var angle:Number = (VA.x * VB.x + VA.y * VB.y)/(Math.sqrt(VA.x * VA.x + VA.y * VA.y)*Math.sqrt(VB.x * VB.x + VB.y * VB.y));
			if(angle > 1)
				return 0;
			else if(angle < -1)
				return Math.PI;
			else
			{
				return Math.acos(angle);
			}
		}
		
		public static function pointIsOnTheLine(LinePA:Point, linePB:Point, testPoint:Point):Boolean
		{
			var lineVector:Vector.<Number> = buildLineAccrodingTwoPoints(LinePA, linePB);
			var A:Number = lineVector[0];
			var B:Number = lineVector[1];
			var C:Number = lineVector[2];
			if(PolygonMath.equal(A*testPoint.x + B*testPoint.y + C,0))
			{
				if(testPoint.x >= Math.min(LinePA.x,linePB.x)&&testPoint.x <= Math.max(LinePA.x,linePB.x)
					&&testPoint.y >= Math.min(LinePA.y,linePB.y)&&testPoint.y <= Math.max(LinePA.y,linePB.y))
				{
					return true;
				}
			}
			return false;
		}
		
		public static function pointIsOntheEdge(point:Point, edgePointA:Point, edgePointB:Point):Boolean
		{
			var lineVector:Vector.<Number> = buildLineAccrodingTwoPoints(edgePointA, edgePointB);
			var A:Number = lineVector[0];
			var B:Number = lineVector[1];
			var C:Number = lineVector[2];
			var tempPoint:Point = new Point();
			tempPoint.x = (B*B*point.x-A*B*point.y-A*C)/(A*A+B*B);
			tempPoint.y = (A*A*point.y-A*B*point.x-B*C)/(A*A+B*B);
			if(A == 0)
			{
				if(tempPoint.x <= Math.max(edgePointA.x, edgePointB.x) && tempPoint.x >= Math.min(edgePointA.x, edgePointB.x))
					return true;
				else
					return false;
			}
			else if(B == 0)
			{
				if(tempPoint.y <= Math.max(edgePointA.y, edgePointB.y) && tempPoint.y >= Math.min(edgePointA.y, edgePointB.y))
					return true;
				else
					return false;
			}
			else 
			{
				if(tempPoint.x <= Math.max(edgePointA.x, edgePointB.x) && tempPoint.x >= Math.min(edgePointA.x, edgePointB.x) 
					&& tempPoint.y <= Math.max(edgePointA.y, edgePointB.y) && tempPoint.y >= Math.min(edgePointA.y, edgePointB.y))
				{
					return true;
				}
				else
				{
					return false;
				}
			}
		}
		
		public static function rotationAngle(testPoint:DListNode, edgePointA:DListNode, edgePointB:DListNode):Number
		{
			var tempX1:Number = testPoint.prev.data.globalX - testPoint.data.globalX;
			var tempX2:Number = - testPoint.next.data.globalX + testPoint.data.globalX;
			var tempY1:Number = testPoint.prev.data.globalY - testPoint.data.globalY;
			var tempY2:Number = -testPoint.next.data.globalY + testPoint.data.globalY;
			
			var eX:Number = edgePointA.data.globalX - edgePointB.data.globalX;
			var eY:Number = edgePointA.data.globalY - edgePointB.data.globalY;
			var angleA:Number = Math.acos(Math.abs((tempX1*eX + tempY1*eY)/Math.sqrt((tempX1*tempX1+tempY1*tempY1)*(eX*eX+eY*eY))));
			var angleB:Number = Math.acos(Math.abs((tempX2*eX + tempY2*eY)/Math.sqrt((tempX2*tempX2+tempY2*tempY2)*(eX*eX+eY*eY))));
			
			if (angleA <= angleB)
			{
				return -angleA;
			}
			else
			{
				return angleB;
			}
		}
		
		public static function pedal(linePointA:Point, linePointB:Point, sourcePoint:Point):Point
		{
			var coefficientVector:Vector.<Number> = buildLineAccrodingTwoPoints(linePointA,linePointB);
			var A:Number = coefficientVector[0];
			var B:Number = coefficientVector[1];
			var C:Number = coefficientVector[2];
			var pedal:Point = new Point;
			pedal.x = (B*B*sourcePoint.x-A*B*sourcePoint.y-A*C)/(A*A+B*B);
			pedal.y = (A*A*sourcePoint.y-A*B*sourcePoint.x-B*C)/(A*A+B*B);
			return pedal;
		}
		
		public static function pointToLineSquareDistance(linePointA:Point, linePointB:Point, testPoint:Point):Number
		{
			var coefficientVector:Vector.<Number> = buildLineAccrodingTwoPoints(linePointA,linePointB);
			var A:Number = coefficientVector[0];
			var B:Number = coefficientVector[1];
			var C:Number = coefficientVector[2];
			var temp:Number = A*testPoint.x + B*testPoint.y + C;
			var distance:Number = temp*temp/(A*A+B*B);
			return distance;
		}
		//返回与resouceVector垂直的两向量中任意一个向量，且返回结果是经过规范化的
		public static function verticalVector(resouceVector:Point):Point
		{
			if(resouceVector.y)
			{
				var temp:Point = new Point(1, -resouceVector.x / resouceVector.y);
				return new Point(temp.x / temp.length, temp.y / temp.length);
			}
			else
			{
				return new Point(0,1);
			}
		}
		//判断三角形与矩形是否相交
		public static function triangleIntersecRectangle(triangle:Vector.<Point>, rectangle:Vector.<Point>):Boolean
		{
			if(!lineAcrossRectangle(triangle[0],triangle[1],rectangle) &&
				!lineAcrossRectangle(triangle[1],triangle[2],rectangle) &&
				!lineAcrossRectangle(triangle[2],triangle[0],rectangle))
				return false;
			return true;	
		}
		
		//判断直线是否与矩形相交
		public static function lineAcrossRectangle(linePointA:Point,linePointB:Point, rectangle:Vector.<Point>):Boolean
		{
			if(!edgeIntersect(linePointA,linePointB,rectangle[0], rectangle[2]) &&
				!edgeIntersect(linePointA,linePointB,rectangle[1], rectangle[3]) )
				return false;
			
			return true;
		}
		
		public static function pointToRectangleDistance(point:Point,box:Vector.<Point>):Number 
		{
			var nx:Point = box[1].subtract(box[0]);
			var ny:Point = box[2].subtract(box[1]);
			var originPoint:Point = new Point((box[0].x+box[2].x)/2, (box[0].y+box[2].y)/2);
			var newBox:Vector.<Point> = new Vector.<Point>();
			newBox.push(box[0].subtract(originPoint), box[1].subtract(originPoint), 
				box[2].subtract(originPoint),box[3].subtract(originPoint));
			
			var dis:Point = point.subtract(new Point((box[0].x+box[2].x)/2, (box[0].y + box[2].y)/2));
			nx.normalize(1);
			ny.normalize(1);
			var newPos:Point =new Point(dis.x*nx.x + dis.y*nx.y,  dis.x*ny.x + dis.y*ny.y);
			var left:Number = newBox[0].x*nx.x + newBox[0].y*nx.y;
			var right:Number = newBox[2].x*nx.x + newBox[2].y*nx.y;
			var top:Number = newBox[0].x*ny.x + newBox[0].y*ny.y;
			var bottom:Number = newBox[2].x*ny.x + newBox[2].y*ny.y;
			if(newPos.x < Math.max(right,left) && newPos.x > Math.min(left, right))
			{
				if(newPos.y < Math.max(top,bottom) && newPos.y > Math.min(top,bottom))
					return 0;
				
				return Math.min(Math.abs(newPos.y - top), Math.abs(newPos.y - bottom));
			}
			else if(newPos.y < Math.max(top,bottom) && newPos.y > Math.min(top,bottom) )
			{
				return Math.min(Math.abs(newPos.x - left),Math.abs(newPos.x - right));
			}
			else if(newPos.x < left)
			{
				return Math.min(point.subtract(box[0]).length, point.subtract(box[3]).length);
			}
			else
				return Math.min(point.subtract(box[1]).length, point.subtract(box[2]).length);
		}
		
		//点在圆内部判断,在内部返回true
		public static function pointInCircular(point:Point,radius:Number,circularCenter:Point):Boolean 
		{
			if((point.subtract(circularCenter)).length <= radius)
				return true;
			else
				return false;
		}
	}
}